import functools

# 超出时间限制:34/50

MOD = 10 ** 9 + 7

# 计算可能用到的阶乘列表
factorials = [1]
factorials_inv = [1]  # 阶乘的乘法逆元
for num in range(1, 1001):
    factorials.append((factorials[-1] * num) % MOD)
    factorials_inv.append(pow(factorials[-1], MOD - 2, MOD))


def comb(n, m):
    return factorials[n] * factorials_inv[m]


@functools.lru_cache(maxsize=None)
def count(n, k):
    # 如果需要看到的比有的多：无法实现
    if n < k:
        return 0

    # 当前列表中所有都必须看到：有序递增
    if n == k:
        return 1

    # 当前列表中只能被看到1个：第1个为最大的，后面全排列
    if k == 1:
        return factorials[n - 1]

    # 当前列表中1个都不能被看到：无法实现
    if k == 0:
        return 0

    # 计算第一个可以放置的最大的数
    first_max = n - k + 1

    ans = 0

    for i in range(1, first_max + 1):
        # 计算比第1个位置小的数量
        smaller = i - 1

        # 计算比第1个位置大的数量
        bigger = n - i

        # 后面排列的能看见的情况总数
        num1 = count(bigger, k - 1)

        # 把n个比第1个位置小的随意插入m个比第1个位置大的数中
        # n = smaller
        # m = bigger+1
        if smaller == 0:
            v2 = 1
        else:
            # n = smaller + bigger ; m = bigger
            v2 = factorials[smaller + bigger] * factorials_inv[bigger] * factorials_inv[smaller]

        num2 = num1 * factorials[smaller] * v2

        # print([n, k], ":", i, "->", [bigger, k - 1], "->", num1, ",", v1, v2, "->", num2)

        ans += num2 % MOD

    return ans % MOD


class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        return count(n, k)


if __name__ == "__main__":
    print(Solution().rearrangeSticks(3, 2))  # 3
    print(Solution().rearrangeSticks(5, 5))  # 1
    print(Solution().rearrangeSticks(20, 11))  # 647427950

    # 自制用例
    print(Solution().rearrangeSticks(4, 2))  # 11

    # 测试用例14/50
    print(Solution().rearrangeSticks(105, 20))  # 680986848

    # 测试用例30/50
    print(Solution().rearrangeSticks(469, 311))  # 334833811

    # 测试用例34/50
    print(Solution().rearrangeSticks(964, 564))  #
